package com.atguigui.leetcode1;

import java.util.ArrayList;

/**
 * 143.重排链表
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/7/31 8:58
 */
public class P143ReorderList {


    class Solution {
        public void reorderList(ListNode head) {

            if (head == null) {
                return;
            }

            ArrayList<ListNode> list = new ArrayList<>();
            ListNode node = head;
            while (node != null) {
                list.add(node);
                node = node.next;
            }

            int l = 0, r = list.size() - 1;
            while (l < r) {
                list.get(l).next = list.get(r);
                l++;
                if (l == r) {
                    break;
                }
                list.get(r).next = list.get(l);
                r--;
            }

            list.get(l).next = null;
        }
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
